
//? 最好O(nlog2n) 最坏O(n2) 不稳定 空间O(log2n)   将快速排序变稳定的方法是新建一个数组，用于保存相同数字，通过索引分先后。
function quickSort(nums) {
    //? 递归出口
    if (nums.length <= 1) return nums
    let mid = 0
    let left = []
    let right = []
    for (let i = 1; i < nums.length; i ++) {
        if (nums[i] < nums[mid]) {
            left.push(nums[i])
        }
        else {
            right.push(nums[i])
        }
    }
    //? 返回的是左边的排序结果 + key值 + 右边的排序结果
    return [...quickSort(left), nums[mid], ...quickSort(right)]
}



console.log(quickSort([4, 2, 8, 9, 1, 7, 10, 3, 0, 2]));
